/**
 * @param {number} n
 * @return {number}
 */
var fib1 = function (n) {
  if (n === 0) return 0
  if (n === 1) return 1
  return fib(n - 1) + fib(n - 2)
};

var fib2 = function (n) {
  let temp = [0, 1]
  let result = temp[n]
  if (typeof result !== 'number') {
    result = fib2(n - 1) + fib2(n - 2)
    temp[n] = result // 缓存
  }
  return result
};



// 优化

// int fib(int N) {
//   if (N < 1) return 0;
//   // 备忘录全初始化为 0
//   vector < int > memo(N + 1, 0);
//   // 进行带备忘录的递归
//   return helper(memo, N);
// }

// int helper(vector < int >& memo, int n) {
//   // base case 
//   if (n == 1 || n == 2) return 1;
//   // 已经计算过
//   if (memo[n] != 0) return memo[n];
//   memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
//   return memo[n];
// }

